{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<font size=6>循环神经网络（Recurrent Neural Networks-RNN）</font>\n",
    "# 为什么需要RNN？\n",
    "## 序列数据\n",
    "序列是相互依赖的（有限或无限）数据流，比如时间序列数据、信息性的字符串、对话等。在对话中，一个句子可能有一个意思，但是整体的对话可能又是完全不同的意思。股市数据这样的时间序列数据也是，单个数据表示当前价格，但是全天的数据会有不一样的变化，促使我们作出买进或卖出的决定。\n",
    "\n",
    "RNN面对的场景是，输入数据具有依赖性且是序列模式。RNN突出的特点是其记忆性，就是 对之前发生在数据序列中的事是有一定的记忆。这有助于系统获取上下文。理论上讲，RNN 有无限的记忆，这意味着有无限回顾的能力。通过回顾可以了解所有之前的输入。\n",
    "## 应用场景\n",
    "<img src=\"images/ae2970d80a119cd341ef31c684bfac49.png\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# one-hot向量\n",
    "**目标：**识别单词是否名词；"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "# 样本\n",
    "sample=\"to be a quant you have to be good at coding and finance\"\n",
    "# 分词\n",
    "words=sample.split(\" \")\n",
    "# 词典\n",
    "token={j:i for i,j in enumerate(set(words))}\n",
    "# 词向量\n",
    "seq=np.zeros(shape=(len(token),len(words)))\n",
    "for i,j in enumerate(words):\n",
    "    seq[token.get(j),i]=1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'a': 0,\n",
       " 'you': 1,\n",
       " 'have': 2,\n",
       " 'quant': 3,\n",
       " 'finance': 4,\n",
       " 'good': 5,\n",
       " 'to': 6,\n",
       " 'be': 7,\n",
       " 'coding': 8,\n",
       " 'and': 9,\n",
       " 'at': 10}"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "token"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[0., 0., 1., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0.],\n",
       "       [0., 0., 0., 0., 1., 0., 0., 0., 0., 0., 0., 0., 0.],\n",
       "       [0., 0., 0., 0., 0., 1., 0., 0., 0., 0., 0., 0., 0.],\n",
       "       [0., 0., 0., 1., 0., 0., 0., 0., 0., 0., 0., 0., 0.],\n",
       "       [0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 1.],\n",
       "       [0., 0., 0., 0., 0., 0., 0., 0., 1., 0., 0., 0., 0.],\n",
       "       [1., 0., 0., 0., 0., 0., 1., 0., 0., 0., 0., 0., 0.],\n",
       "       [0., 1., 0., 0., 0., 0., 0., 1., 0., 0., 0., 0., 0.],\n",
       "       [0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 1., 0., 0.],\n",
       "       [0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 1., 0.],\n",
       "       [0., 0., 0., 0., 0., 0., 0., 0., 0., 1., 0., 0., 0.]])"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "seq"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 符号\n",
    "$\\large x^{(i)}$:第i个样本；\n",
    "\n",
    "$\\large x^{[i]}$:第i层；\n",
    "\n",
    "$\\large x^{\\{i\\}}$:第i批；\n",
    "\n",
    "$\\large x^{<i>}$:序列的第i个位置；\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# RNN Model\n",
    "## 准备\n",
    "1. 目标：判断一个句子里面的单词是否是名词；\n",
    "2. 传统NN只能根据样本标记判断单词词性，忽略了语境的作用，这正是RNN的特长；\n",
    "\n",
    "## RNN\n",
    "<img src=\"images/07e3288e16d576a545d03e5127adbb91.png\">\n",
    "\n",
    "### 特点\n",
    "1. $\\large a^{<0>}$：初始化为零向量；\n",
    "2. $\\large \\hat y^{<t>}=f(x^{<t>},a^{<t-1>})$\n",
    "\n",
    "## RNN前向传播\n",
    "<img src=\"images/aad5728eb983cfabfac6fc38e90d28ff.png\">\n",
    "\n",
    "$\\large a^{< t >} = g_{1}(W_{aa}a^{< t - 1 >} + W_{ax}x^{< t >} + b_{a})$\n",
    "\n",
    "$\\large \\hat y^{<t>} = g_{2}(W_{ya}a^{< t >} + b_{y})$\n",
    "\n",
    "$\\large 令：W_{a}=\\left [W_{aa},W_{ax}\\right ],\\left\\lbrack a^{< t - 1 >},x^{< t >}\\right\\rbrack=\\begin{bmatrix}a^{< t-1 >} \\\\ x^{< t >} \\\\\\end{bmatrix}$\n",
    "\n",
    "$\\large 那么：\\\\\\large a^{< t >} = g_{1}(W_{a}\\left\\lbrack a^{< t - 1 >},x^{< t >}\\right\\rbrack + b_{a})\\\\\\large\\hat y^{<t>} = g_{2}(W_{y}a^{< t >} + b_{y})$\n",
    "\n",
    "### 形状\n",
    "$\\because\\\\x^{<t>}:(n,1)\\\\a^{t-1}:(m,1)\\\\W_{a}:(m,n+m)\\\\b_{a}:(m,1)\\\\W_{y}:(1,m)\\\\b_{y}:(1,1)\\\\\\therefore\\\\a^{<t>}:(m,1)\\to a^{<t>}的形状自洽\\\\\\hat y^{<t>}:(1,1)$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## RNN反向传播\n",
    "1. 链式法则；\n",
    "2. 传播顺序；\n",
    "3. **注意：参数在各单元是共享的；**\n",
    "\n",
    "### 传播流\n",
    "<img src=\"images/998c7af4f90cd0de0c88f138b61f0168.png\">\n",
    "\n",
    "### 损失函数\n",
    "$L^{<t>}( \\hat y^{<t>},y^{<t>}) = - y^{<t>}\\log\\hat  y^{<t>}-( 1-\\hat y^{<t>})log(1-\\hat y^{<t>})$\n",
    "### 成本函数\n",
    "$L(\\hat y,y) = \\sum_{t = 1}^{T_{x}}{L^{< t >}(\\hat  y^{< t >},y^{< t >})}$\n",
    "### 序列$t$位置/时刻的反向传播\n",
    "<img src=\"images/4235dc87f795faabe628a91cd1a681f6.png\">\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 不同类型的循环神经网络\n",
    "1. 按照输入和输出数量来分类；\n",
    "<img src=\"images/1daa38085604dd04e91ebc5e609d1179.png\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 循环神经网络的梯度消失\n",
    "**原因：**\n",
    "1. 时间序列的长度；\n",
    "2. 连乘效应；\n",
    "\n",
    "**解决方法：**\n",
    "1. 通用方法,eg.加速下降，L2正则化；\n",
    "2. 门值调节；"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# **GRU**（Gated Recurrent Unit）\n",
    "$\\Gamma_u=\\sigma(W_u[a^{<t-1>},x^{<t>}]+b_u)\\\\\n",
    "\\Gamma_r=\\sigma(W_r[a^{<t-1>},x^{<t>}]+b_r)\\\\\n",
    "\\tilde c^{<t>}=tanh(W_{c}[\\Gamma_ra^{<t-1>},x^{<t>}]+b_c)\\\\\n",
    "c^{<t>} =\\Gamma_{u}{\\tilde{c}}^{<t>} + (1-\\Gamma_{u})c^{<t-1>}\\\\\n",
    "a^{<t>} =c^{<t>} \n",
    "$\n",
    "\n",
    "**注：**\n",
    "1. **c**：代表细胞（cell），即记忆细胞；\n",
    "2. $\\Gamma_{u}$,代表更新门，这是一个0到1之间的值;\n",
    "3. $\\Gamma_{r}$,代表相关门，这是一个0到1之间的值；"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# LSTM（long short term memory unit）\n",
    "$\\Gamma_u=\\sigma(W_u[a^{<t-1>},x^{<t>}]+b_u)\\\\\n",
    "\\Gamma_f=\\sigma(W_f[a^{<t-1>},x^{<t>}]+b_f)\\\\\n",
    "\\Gamma_o=\\sigma(W_o[a^{<t-1>},x^{<t>}]+b_o)\\\\\n",
    "\\tilde c^{<t>}=tanh(W_{c}[a^{<t-1>},x^{<t>}]+b_c)\\\\\n",
    "c^{<t>} =\\Gamma_{u}{\\tilde{c}}^{<t>} + \\Gamma_{f}c^{<t-1>}\\\\\n",
    "a^{<t>} =\\Gamma_{o}c^{<t>} \n",
    "$\n",
    "\n",
    "**注：**\n",
    "1. **c**：代表细胞（cell），即记忆细胞；\n",
    "2. $\\Gamma_{u}$,代表更新门，这是一个0到1之间的值;\n",
    "3. $\\Gamma_{f}$,代表遗忘门，这是一个0到1之间的值；\n",
    "4. $\\Gamma_{o}$,代表输出门，这是一个0到1之间的值；"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#  双向循环神经网络（Bidirectional **RNN**）\n",
    "RNN和LSTM都只能依据之前时刻的时序信息来预测下一时刻的输出，但在有些问题中，当前时刻的输出不仅和之前的状态有关，还可能和未来的状态有关系。比如预测一句话中缺失的单词不仅需要根据前文来判断，还需要考虑它后面的内容，真正做到基于上下文判断。BRNN有两个RNN上下叠加在一起组成的，输出由这两个RNN的状态共同决定。\n",
    "<img src=\"images/5aa6424f0001485b07120276.png\">\n",
    "## 公式\n",
    "$\\large\\hat y^{<t>}=g(W_{g}\\left\\lbrack {\\overrightarrow{a}}^{<t>},{\\overleftarrow{a}}^{<t>} \\right\\rbrack +b_y)$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 深层循环神经网络（Deep **RNN**s）\n",
    "## 公式\n",
    "$\\large a^{[l]<t>}=g(W_a^{[l]}[a^{[l]<t-1>},a^{[l-1]<t>}]+b_a^{[l]})$\n",
    "## 单层RNN\n",
    "<img src=\"images/616f645e887b51177db8cb6694a5d03b.png\">\n",
    "\n",
    "## 多层RNN\n",
    "<img src=\"images/539b99a27a6e87a5cca9d52b5b2c81c5.png\">\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Basic $RNN$\n",
    "$RNN$因为其“记忆”特性，擅长处理$NLP$(自然语言处理)和其他序列型任务。我们接下来使用$numpy$开发我们的第一个简单的$RNN$。$RNN$类型属于$many-to-many$，输入和输出的序列长度相等，即$T_x=T_y$。\n",
    "<img src=\"images/07e3288e16d576a545d03e5127adbb91.png\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 前向传播-Forward Propagation\n",
    "**步骤：**\n",
    "1. 实现t时序的计算功能；\n",
    "2. 循环遍历所有时序处理时序输入；\n",
    "\n",
    "### RNN cell\n",
    "一个循环神经网络是由单个网络单元，又叫细胞组合而成。我们先来实现单个细胞，如图所示。\n",
    "<img src=\"images/999911c9276922884a7caac8cc28dbff.png\" style=\"width:700px;height:300px;\">\n",
    "\n",
    "**实现RNN cell：**\n",
    "1. 采用激活函数计算隐藏层的激活值（又叫细胞值）：$a^{\\langle t \\rangle} = \\tanh(W_{aa} a^{\\langle t-1 \\rangle} + W_{ax} x^{\\langle t \\rangle} + b_a)$.\n",
    "2. 使用激活值 $a^{\\langle t \\rangle}$, 采用`softmax`，计算预测值 $\\hat{y}^{\\langle t \\rangle} = softmax(W_{ya} a^{\\langle t \\rangle} + b_y)$.\n",
    "3. 缓存 $(a^{\\langle t \\rangle}, a^{\\langle t-1 \\rangle}, x^{\\langle t \\rangle}, parameters)$ .\n",
    "4. 返回 $a^{\\langle t \\rangle}$ , $y^{\\langle t \\rangle}$ 和 缓存.\n",
    "\n",
    "这里，我们向量化$m$个样本，$t$时序输入值$x^{<t>}$的形状为：$(n_x,m)$，并且$t$时序激活值$a^{<t>}$的形状为：$(n_a,m)$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "def rnn_cell_forward(xt, a_prev, parameters):\n",
    "    \"\"\"\n",
    "    细胞单元\n",
    "    参数:\n",
    "    xt -- t时序的输入数据, 形状：(n_x, m).\n",
    "    a_prev -- t-1时序的激活值, 形状：(n_a, m)\n",
    "    parameters -- 字典类型:\n",
    "            Wax -- 计算激活值，与输入相关的权重矩阵, 形状： (n_a, n_x)\n",
    "            Waa -- 计算激活值，与前激活值相关的权重矩阵, 形状： (n_a, n_a)\n",
    "            Wya -- 计算预测值的权重矩阵, 形状： (n_y, n_a)\n",
    "            ba --  计算激活值的偏置项, 形状： (n_a, 1)\n",
    "            by --  就算预测值的偏置项, 形状： (n_y, 1)\n",
    "    返回:\n",
    "    a_next -- 激活值, 形状： (n_a, m)\n",
    "    yt_pred -- t时序的预测值, 形状： (n_y, m)\n",
    "    cache -- 反向传播用到的变量, 包含 (a_next, a_prev, xt, parameters)\n",
    "    \"\"\"    \n",
    "    Wax = parameters[\"Wax\"]\n",
    "    Waa = parameters[\"Waa\"]\n",
    "    Wya = parameters[\"Wya\"]\n",
    "    ba = parameters[\"ba\"]\n",
    "    by = parameters[\"by\"]        \n",
    "    # 计算t时序的激活值\n",
    "    a_next = np.tanh(np.dot(Wax,xt)+np.dot(Waa,a_prev)+ba)\n",
    "    # 计算t时序的预测值\n",
    "    yt_pred = softmax(np.dot(Wya,a_next)+by)       \n",
    "    # 缓存反向传播用的的值\n",
    "    cache = (a_next, a_prev, xt, parameters)    \n",
    "    return a_next, yt_pred, cache"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "def softmax(x):\n",
    "    e_x = np.exp(x)\n",
    "    return e_x / e_x.sum(axis=0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "((5, 10), (2, 10))"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "np.random.seed(1)\n",
    "xt = np.random.randn(3,10)\n",
    "a_prev = np.random.randn(5,10)\n",
    "Waa = np.random.randn(5,5)\n",
    "Wax = np.random.randn(5,3)\n",
    "Wya = np.random.randn(2,5)\n",
    "ba = np.random.randn(5,1)\n",
    "by = np.random.randn(2,1)\n",
    "parameters = {\"Waa\": Waa, \"Wax\": Wax, \"Wya\": Wya, \"ba\": ba, \"by\": by}\n",
    "\n",
    "a_next, yt_pred, cache = rnn_cell_forward(xt, a_prev, parameters)\n",
    "a_next.shape,yt_pred.shape"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 单元集成\n",
    "接下来，我们将上面实现的细胞单元进行集成形成RNN的前向传播。\n",
    "1. 创建激活值内存空间，存储所有时序的细胞激活值；\n",
    "2. 初始化$a^{<0>}$;\n",
    "3. 递增遍历所有时序：\n",
    "    1. 运算`rnn_cell_forward`函数；\n",
    "    2. 得到t时序的激活值、预测值和缓存值；\n",
    "4. 返回所有时序的激活值、预测值和缓存值；"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "def rnn_forward(x, a0, parameters):\n",
    "    \"\"\"\n",
    "    RNN前向传播.\n",
    "    参数:\n",
    "    x -- 输入值, of shape (n_x, m, T_x).\n",
    "    a0 -- 0时序的初始化值, of shape (n_a, m)\n",
    "    参数 -- 字典:\n",
    "           Waa -- 计算激活值，与t-1时序相关的权重矩阵, 形状：(n_a, n_a)\n",
    "           Wax -- 计算激活值，与t时序输入值相关的权重矩阵, 形状：(n_a, n_x)\n",
    "           Wya -- 计算预测值，与t时序激活值相关的权重矩阵, 形状：(n_y, n_a)\n",
    "           ba --  计算激活值的偏置项，形状：(n_a, 1)\n",
    "           by --  计算预测值的偏置项, 形状： (n_y, 1)\n",
    "\n",
    "    返回:\n",
    "    a -- 所有时序的激活值, 形状：(n_a, m, T_x)\n",
    "    y_pred -- 所有时序的预测值, 形状： (n_y, m, T_x)\n",
    "    caches -- 反向传播用到的所有时序的缓存值, 包含 (aches, x)\n",
    "    \"\"\"    \n",
    "    # 初始化缓存空间，缓存所有时序的缓存值\n",
    "    caches = []    \n",
    "    # 获取维度信息\n",
    "    n_x, m, T_x = x.shape\n",
    "    n_y, n_a = parameters[\"Wya\"].shape\n",
    "    \n",
    "    # 初始化激活值和预测值\n",
    "    a = np.zeros((n_a,m,T_x))\n",
    "    y_pred = np.zeros((n_y,m,T_x))\n",
    "    \n",
    "    # 获取0时序的激活值\n",
    "    a_next = a0\n",
    "    \n",
    "    # 升序遍历\n",
    "    for t in range(T_x):\n",
    "        a_next, yt_pred, cache = rnn_cell_forward(x[:,:,t],a_next,parameters)\n",
    "        a[:,:,t] = a_next\n",
    "        y_pred[:,:,t] = yt_pred\n",
    "        caches.append(cache)        \n",
    "    caches = (caches, x)    \n",
    "    return a, y_pred, caches"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "((5, 10, 4), (2, 10, 4), 4)"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "np.random.seed(1)\n",
    "x = np.random.randn(3,10,4)\n",
    "a0 = np.random.randn(5,10)\n",
    "Waa = np.random.randn(5,5)\n",
    "Wax = np.random.randn(5,3)\n",
    "Wya = np.random.randn(2,5)\n",
    "ba = np.random.randn(5,1)\n",
    "by = np.random.randn(2,1)\n",
    "parameters = {\"Waa\": Waa, \"Wax\": Wax, \"Wya\": Wya, \"ba\": ba, \"by\": by}\n",
    "\n",
    "a, y_pred, caches = rnn_forward(x, a0, parameters)\n",
    "a.shape,y_pred.shape,len(caches[0])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 反向传播-Back Propagation\n",
    "### RNN cell\n",
    "同前向传播一样，我们先建立t时序单元细胞的反向传播计算。这里需要用到如下求导等式：\n",
    "1. $tanh^{'}(x)=1-tanh{(x)}^2$;\n",
    "<img src=\"images/4235dc87f795faabe628a91cd1a681f6.png\">"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "def rnn_cell_backward(da_next, cache):\n",
    "    (a_next, a_prev, xt, parameters) = cache\n",
    "    \n",
    "    Wax = parameters[\"Wax\"]\n",
    "    Waa = parameters[\"Waa\"]\n",
    "    Wya = parameters[\"Wya\"]\n",
    "    ba = parameters[\"ba\"]\n",
    "    by = parameters[\"by\"]\n",
    "    # 中间变量求导\n",
    "    dtanh = (1-a_next*a_next)*da_next\n",
    "    # 输入值和输入相关权重求导\n",
    "    dxt = np.dot(Wax.T,  dtanh)\n",
    "    dWax = np.dot(dtanh,xt.T)\n",
    "    # t-1时序激活值和激活相关权重求导\n",
    "    da_prev = np.dot(Waa.T, dtanh)\n",
    "    dWaa = np.dot( dtanh,a_prev.T)\n",
    "    # 截距项求导\n",
    "    dba = np.sum( dtanh,keepdims=True,axis=-1)\n",
    "\n",
    "    gradients = {\"dxt\": dxt, \"da_prev\": da_prev, \"dWax\": dWax, \"dWaa\": dWaa, \"dba\": dba}\n",
    "    \n",
    "    return gradients"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "((3, 10), (5, 10), (5, 3), (5, 5), (5, 1))"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "np.random.seed(1)\n",
    "xt = np.random.randn(3,10)\n",
    "a_prev = np.random.randn(5,10)\n",
    "Wax = np.random.randn(5,3)\n",
    "Waa = np.random.randn(5,5)\n",
    "Wya = np.random.randn(2,5)\n",
    "b = np.random.randn(5,1)\n",
    "by = np.random.randn(2,1)\n",
    "parameters = {\"Wax\": Wax, \"Waa\": Waa, \"Wya\": Wya, \"ba\": ba, \"by\": by}\n",
    "\n",
    "a_next, yt, cache = rnn_cell_forward(xt, a_prev, parameters)\n",
    "\n",
    "da_next = np.random.randn(5,10)\n",
    "gradients = rnn_cell_backward(da_next, cache)\n",
    "gradients[\"dxt\"].shape,gradients[\"da_prev\"].shape,gradients['dWax'].shape,gradients['dWaa'].shape,gradients['dba'].shape"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 单元集成\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "def rnn_backward(da, caches):\n",
    "    (caches, x) = caches\n",
    "    (a1, a0, x1, parameters) = caches[0]  # t=1 时的值\n",
    "\n",
    "    n_a, m, T_x = da.shape\n",
    "    n_x, m = x1.shape\n",
    "\n",
    "    dx = np.zeros((n_x, m, T_x))\n",
    "    dWax = np.zeros((n_a, n_x))\n",
    "    dWaa = np.zeros((n_a, n_a))\n",
    "    dba = np.zeros((n_a, 1))\n",
    "    da0 = np.zeros((n_a, m))\n",
    "    da_prevt = np.zeros((n_a, m))\n",
    "\n",
    "    for t in reversed(range(T_x)):\n",
    "        gradients = rnn_cell_backward(da[:, :, t] + da_prevt, caches[t]) \n",
    "        dxt, da_prevt, dWaxt, dWaat, dbat =\\\n",
    "        gradients[\"dxt\"], gradients[\"da_prev\"], gradients[\"dWax\"], gradients[\"dWaa\"], gradients[\"dba\"]\n",
    "        dx[:, :, t] = dxt\n",
    "        dWax += dWaxt\n",
    "        dWaa += dWaat\n",
    "        dba += dbat\n",
    "        \n",
    "    da0 = da_prevt\n",
    "\n",
    "    gradients = {\"dx\": dx, \"da0\": da0, \"dWax\": dWax, \"dWaa\": dWaa,\"dba\": dba}\n",
    "    \n",
    "    return gradients"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "((3, 10, 4), (5, 10), (5, 3), (5, 5), (5, 1))"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "np.random.seed(1)\n",
    "x = np.random.randn(3,10,4)\n",
    "a0 = np.random.randn(5,10)\n",
    "Wax = np.random.randn(5,3)\n",
    "Waa = np.random.randn(5,5)\n",
    "Wya = np.random.randn(2,5)\n",
    "ba = np.random.randn(5,1)\n",
    "by = np.random.randn(2,1)\n",
    "parameters = {\"Wax\": Wax, \"Waa\": Waa, \"Wya\": Wya, \"ba\": ba, \"by\": by}\n",
    "a, y, caches = rnn_forward(x, a0, parameters)\n",
    "da = np.random.randn(5, 10, 4)\n",
    "gradients = rnn_backward(da, caches)\n",
    "\n",
    "gradients[\"dx\"].shape,gradients[\"da0\"].shape,gradients[\"dWax\"].shape,gradients[\"dWaa\"].shape,gradients[\"dba\"].shape"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "到现在，我们已经初步完成了Basic RNN Model。该算法对于简单的应用已经足够了，但是对于一定时序长度的应用，还存在梯度消失的问题，也就是说，RNN的记忆性更多的表现为“短期记忆”。\n",
    "\n",
    "下面，我们建立一个相对复杂的`LSTM`模型，它更擅长处理梯度消失的问题。`LSTM`模型在记忆的特性上表现较好。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Long Short-Term Memory (LSTM) network\n",
    "## LSTM CELL\n",
    "<img src=\"images/eca9158c08600cd86442dfd1c18a3c86.png\" style=\"width:500;height:400px;\">"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [],
   "source": [
    "def lstm_cell_forward(xt, a_prev, c_prev, parameters):\n",
    "    \"\"\"\n",
    "    LSTM cell 细胞单元。\n",
    "    参数:\n",
    "    xt -- t时序的输入值, 形状：(n_x, m).\n",
    "    a_prev -- t-1时序的激活值, 形状： (n_a, m)\n",
    "    c_prev -- t-1时序的细胞值, 形状： (n_a, m)\n",
    "    parameters -- 字典:\n",
    "              Wf -- 遗忘门的权重矩阵, 形状： (n_a, n_a + n_x)\n",
    "              bf -- 遗忘门的截距项, 形状： (n_a, 1)\n",
    "              Wu -- 更新门的权重矩阵, 形状： (n_a, n_a + n_x)\n",
    "              bu -- 更新门的截距项, 形状： (n_a, 1)\n",
    "              Wc -- 计算细胞候选值的权重矩阵, 形状： (n_a, n_a + n_x)\n",
    "              bc -- 计算细胞候选值的截距项, 形状： (n_a, 1)\n",
    "              Wo -- 输出门的权重矩阵, 形状： (n_a, n_a + n_x)\n",
    "              bo -- 输出门的截距项, 形状： (n_a, 1)\n",
    "              Wy -- 与激活值相关，计算预测值的权重矩阵, 形状： (n_y, n_a)\n",
    "              by -- 与激活值相关，计算预测值的截距项, 形状： (n_y, 1)                        \n",
    "    返回:\n",
    "    a_next -- t时序的激活值, of shape (n_a, m)\n",
    "    c_next -- t时序的细胞值, of shape (n_a, m)\n",
    "    yt_pred -- t时序的预测值, numpy array of shape (n_y, m)\n",
    "    cache -- 反向传播需要的变量, 包含 (a_next, c_next, a_prev, c_prev, xt, parameters)\n",
    "    \n",
    "    注意: ft/ut/ot 分别表示 遗忘/更新/输出 门值, cct 表示 细胞值候选值,c 表示细胞值.\n",
    "    \"\"\"\n",
    "    # 检索参数\n",
    "    Wf = parameters[\"Wf\"]\n",
    "    bf = parameters[\"bf\"]\n",
    "    Wu = parameters[\"Wu\"]\n",
    "    bu = parameters[\"bu\"]\n",
    "    Wc = parameters[\"Wc\"]\n",
    "    bc = parameters[\"bc\"]\n",
    "    Wo = parameters[\"Wo\"]\n",
    "    bo = parameters[\"bo\"]\n",
    "    Wy = parameters[\"Wy\"]\n",
    "    by = parameters[\"by\"]\n",
    "    \n",
    "    # 检索形状信息\n",
    "    n_x, m = xt.shape\n",
    "    n_y, n_a = Wy.shape\n",
    "\n",
    "    # 拼接t-1时序激活值和t时序输入值\n",
    "    concat = np.zeros((n_x+n_a,m))\n",
    "    concat[: n_a, :] = a_prev\n",
    "    concat[n_a :, :] = xt\n",
    "\n",
    "    ft = sigmoid(np.dot(Wf,concat)+bf)\n",
    "    ut = sigmoid(np.dot(Wu,concat)+bu)\n",
    "    cct = np.tanh(np.dot(Wc,concat)+bc)\n",
    "    c_next = ft*c_prev + ut*cct\n",
    "    ot = sigmoid(np.dot(Wo,concat)+bo)\n",
    "    a_next = ot*np.tanh(c_next)\n",
    "\n",
    "    yt_pred = softmax(np.dot(Wy, a_next) + by)\n",
    "\n",
    "    cache = (a_next, c_next, a_prev, c_prev, ft, ut, cct, ot, xt, parameters)\n",
    "\n",
    "    return a_next, c_next, yt_pred, cache"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [],
   "source": [
    "def sigmoid(x):\n",
    "    return 1 / (1 + np.exp(-x))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "((5, 10), (5, 10), (2, 10), 10)"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "np.random.seed(1)\n",
    "xt = np.random.randn(3,10)\n",
    "a_prev = np.random.randn(5,10)\n",
    "c_prev = np.random.randn(5,10)\n",
    "Wf = np.random.randn(5, 5+3)\n",
    "bf = np.random.randn(5,1)\n",
    "Wu = np.random.randn(5, 5+3)\n",
    "bu = np.random.randn(5,1)\n",
    "Wo = np.random.randn(5, 5+3)\n",
    "bo = np.random.randn(5,1)\n",
    "Wc = np.random.randn(5, 5+3)\n",
    "bc = np.random.randn(5,1)\n",
    "Wy = np.random.randn(2,5)\n",
    "by = np.random.randn(2,1)\n",
    "\n",
    "parameters = {\"Wf\": Wf, \"Wu\": Wu, \"Wo\": Wo, \"Wc\": Wc, \"Wy\": Wy, \"bf\": bf, \"bu\": bu, \"bo\": bo, \"bc\": bc, \"by\": by}\n",
    "\n",
    "a_next, c_next, yt, cache = lstm_cell_forward(xt, a_prev, c_prev, parameters)\n",
    "a_next.shape,c_next.shape,yt.shape,len(cache)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 单元集成\n",
    "\n",
    "<img src=\"images/ecf8f17d1a32382fac8022d6fc9423a9.png\" style=\"width:500;height:300px;\">\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [],
   "source": [
    "def lstm_forward(x, a0, parameters):\n",
    "    caches = []\n",
    "    \n",
    "    n_x, m, T_x = x.shape\n",
    "    n_y, n_a = parameters['Wy'].shape\n",
    "    \n",
    "    # 初始化激活值、细胞值、预测值\n",
    "    a = np.zeros((n_a, m, T_x))\n",
    "    c = np.zeros((n_a, m, T_x))\n",
    "    y = np.zeros((n_y, m, T_x))\n",
    "    \n",
    "    # 初始化t-1时序的激活值和细胞值\n",
    "    a_next = a0\n",
    "    c_next = np.zeros((n_a, m))\n",
    "    \n",
    "    # 升序遍历\n",
    "    for t in range(T_x):\n",
    "        a_next, c_next, yt, cache = lstm_cell_forward(x[:, :, t], a_next, c_next, parameters)\n",
    "        a[:,:,t] = a_next\n",
    "        y[:,:,t] = yt\n",
    "        c[:,:,t]  = c_next\n",
    "        caches.append(cache)\n",
    "    caches = (caches, x)\n",
    "\n",
    "    return a, y, c, caches"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "((5, 10, 7), (5, 10, 7), (2, 10, 7), 7)"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "np.random.seed(1)\n",
    "x = np.random.randn(3,10,7)\n",
    "a0 = np.random.randn(5,10)\n",
    "Wf = np.random.randn(5, 5+3)\n",
    "bf = np.random.randn(5,1)\n",
    "Wu = np.random.randn(5, 5+3)\n",
    "bu = np.random.randn(5,1)\n",
    "Wo = np.random.randn(5, 5+3)\n",
    "bo = np.random.randn(5,1)\n",
    "Wc = np.random.randn(5, 5+3)\n",
    "bc = np.random.randn(5,1)\n",
    "Wy = np.random.randn(2,5)\n",
    "by = np.random.randn(2,1)\n",
    "\n",
    "parameters = {\"Wf\": Wf, \"Wu\": Wu, \"Wo\": Wo, \"Wc\": Wc, \"Wy\": Wy, \"bf\": bf, \"bu\": bu, \"bo\": bo, \"bc\": bc, \"by\": by}\n",
    "\n",
    "a, y, c, caches = lstm_forward(x, a0, parameters)\n",
    "a.shape,c.shape,y.shape,len(caches[0])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 反向传播\n",
    "略"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 生成文本\n",
    "自动给恐龙取名字。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 环境配置"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import random\n",
    "from random import shuffle"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 加载处理数据"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(19909, 27)"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# 读取文本\n",
    "with open('datasets/dinos.txt', 'r') as f:\n",
    "    data =f.read()\n",
    "data= data.lower()# 转为小写\n",
    "chars = list(set(data))# 获取字符列表\n",
    "len(data), len(chars)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 索引字符\n",
    "\"\\n\"表示名字的结尾。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [],
   "source": [
    "char_to_ix = { ch:i for i,ch in enumerate(sorted(chars)) }\n",
    "ix_to_char = { i:ch for i,ch in enumerate(sorted(chars)) }"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 梯度裁剪\n",
    "防止梯度爆炸。\n",
    "<img src=\"images/f6d8b886335927d46fad323c60335d09.png\" style=\"width:400;height:150px;\">\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([-10,   4,  10])"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "x=np.array([-11,4,12])\n",
    "x=np.clip(x,a_min=-10,a_max=10)\n",
    "x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [],
   "source": [
    "def clip(gradients, maxValue):    \n",
    "    dWaa, dWax, dWya, db, dby = gradients['dWaa'], gradients['dWax'], gradients['dWya'], gradients['db'], gradients['dby']\n",
    "    for gradient in [dWax, dWaa, dWya, db, dby]:\n",
    "        np.clip(gradient,-maxValue , maxValue, out=gradient) \n",
    "    gradients = {\"dWaa\": dWaa, \"dWax\": dWax, \"dWya\": dWya, \"db\": db, \"dby\": dby}    \n",
    "    return gradients"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'dWaa': array([[ 10.        ,   8.70969803,  -5.08457134,   7.77419205,\n",
       "          -1.18771172],\n",
       "        [ -1.98998184,  10.        ,  -4.18937898,  -4.79184915,\n",
       "         -10.        ],\n",
       "        [-10.        ,   4.51122939,  -6.94920901,   5.15413802,\n",
       "         -10.        ],\n",
       "        [ -7.67309826,   6.74570707,  10.        ,   5.92472801,\n",
       "          10.        ],\n",
       "        [ 10.        ,  10.        ,  -9.18440038,  -1.05344713,\n",
       "           6.30195671]]),\n",
       " 'dWax': array([[  6.74396105,  -7.22391905,  10.        ],\n",
       "        [ -9.0163449 ,  -8.22467189,   7.21711292],\n",
       "        [ -6.25342001,  -5.93843067,  -3.43900709],\n",
       "        [-10.        ,  10.        ,   6.08514698],\n",
       "        [ -0.69328697,  -1.08392067,   4.50155513]]),\n",
       " 'dWya': array([[ -4.14846901,   4.51946037, -10.        ,  -8.28627979,\n",
       "           5.28879746],\n",
       "        [-10.        , -10.        ,  -0.17718318, -10.        ,\n",
       "           0.57120996]]),\n",
       " 'db': array([[-7.99547491],\n",
       "        [-2.91594596],\n",
       "        [-2.58982853],\n",
       "        [ 1.89293198],\n",
       "        [-5.63788735]]),\n",
       " 'dby': array([[ 0.89686407],\n",
       "        [-6.01156801]])}"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "dWax = np.random.randn(5,3)*10\n",
    "dWaa = np.random.randn(5,5)*10\n",
    "dWya = np.random.randn(2,5)*10\n",
    "db = np.random.randn(5,1)*10\n",
    "dby = np.random.randn(2,1)*10\n",
    "gradients = {\"dWax\": dWax, \"dWaa\": dWaa, \"dWya\": dWya, \"db\": db, \"dby\": dby}\n",
    "clip(gradients, 10)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 如何生成文本？\n",
    "<img src=\"images/b10e5461e536f8c93bbf5f025f686eb8.png\" style=\"width:500;height:300px;\">\n",
    "\n",
    "**步骤：**\n",
    "1. 初始化$x^{<1>}=\\vec 0和a^{<0>}=\\vec 0$;\n",
    "2. 前向传播：\n",
    "    1. $ a^{\\langle t+1 \\rangle} = \\tanh(W_{ax}  x^{\\langle t \\rangle } + W_{aa} a^{\\langle t \\rangle } + b)$\n",
    "    2. $ z^{\\langle t + 1 \\rangle } = W_{ya}  a^{\\langle t + 1 \\rangle } + b_y $\n",
    "    3. $ \\hat{y}^{\\langle t+1 \\rangle } = softmax(z^{\\langle t + 1 \\rangle })$\n",
    "3. 根据$ \\hat{y}^{\\langle t+1 \\rangle }$进行概率抽样获取对应字符；\n",
    "\n",
    "使用`np.random.choice()`:\n",
    "\n",
    "$P(index = 0) = 0.1, P(index = 1) = 0.0, P(index = 2) = 0.7, P(index = 3) = 0.2$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Counter({2: 70, 3: 23, 0: 7})"
      ]
     },
     "execution_count": 24,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from collections import Counter\n",
    "p = np.array([0.1, 0.0, 0.7, 0.2])\n",
    "Counter(np.random.choice([0, 1, 2, 3],size=100, p = p))    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "4. 以第三步获得的抽样字符，经过one-hot转换后，作为下一个时序的输入x；"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [],
   "source": [
    "def sample(parameters, char_to_ix):\n",
    "    Waa, Wax, Wya, by, b = parameters['Waa'], parameters['Wax'], parameters['Wya'], parameters['by'], parameters['b']\n",
    "    vocab_size = by.shape[0]\n",
    "    n_a = Waa.shape[1]\n",
    "\n",
    "    x = np.zeros((vocab_size,1))\n",
    "    a_prev = np.zeros((n_a,1))\n",
    "    \n",
    "    indices = []\n",
    "    \n",
    "    idx = -1 \n",
    "\n",
    "    counter = 0\n",
    "    newline_character = char_to_ix['\\n']\n",
    "    \n",
    "    while (idx != newline_character and counter != 50):\n",
    "\n",
    "        a = np.tanh(np.dot(Wax,x)+np.dot(Waa,a_prev)+b)\n",
    "        z = np.dot(Wya,a)+by\n",
    "        y = softmax(z)\n",
    "                \n",
    "        idx = np.random.choice(range(len(y)),p=y.ravel())\n",
    "\n",
    "        indices.append(idx)\n",
    "        \n",
    "        x = np.zeros((vocab_size,1))\n",
    "        x[idx] = 1\n",
    "        \n",
    "        a_prev = a\n",
    "        \n",
    "        \n",
    "    if (counter == 50):\n",
    "        indices.append(char_to_ix['\\n'])\n",
    "    \n",
    "    return indices"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "('[5, 11, 10, 26, 25, 15, 8, 17, 11, 17, 14, 19, 1, 20, 6, 5, 16, 5, 19, 26, 3, 1, 11, 4, 22, 15, 26, 26, 25, 5, 5, 5, 0]',\n",
       " \"['e', 'k', 'j', 'z', 'y', 'o', 'h', 'q', 'k', 'q', 'n', 's', 'a', 't', 'f', 'e', 'p', 'e', 's', 'z', 'c', 'a', 'k', 'd', 'v', 'o', 'z', 'z', 'y', 'e', 'e', 'e', '\\\\n']\")"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "n, n_a = 20, 100\n",
    "a0 = np.random.randn(n_a, 1)\n",
    "i0 = 1\n",
    "vocab_size=len(chars)\n",
    "Wax, Waa, Wya = np.random.randn(n_a, vocab_size), np.random.randn(n_a, n_a), np.random.randn(vocab_size, n_a)\n",
    "b, by = np.random.randn(n_a, 1), np.random.randn(vocab_size, 1)\n",
    "parameters = {\"Wax\": Wax, \"Waa\": Waa, \"Wya\": Wya, \"b\": b, \"by\": by}\n",
    "\n",
    "indices = sample(parameters, char_to_ix)\n",
    "str(indices),str([ix_to_char[i] for i in indices])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 建立模型"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [],
   "source": [
    "def rnn_step_forward(parameters, a_prev, x):    \n",
    "    Waa, Wax, Wya, by, b = parameters['Waa'], parameters['Wax'], parameters['Wya'], parameters['by'], parameters['b']\n",
    "    a_next = np.tanh(np.dot(Wax, x) + np.dot(Waa, a_prev) + b)\n",
    "    p_t = softmax(np.dot(Wya, a_next) + by) \n",
    "    \n",
    "    return a_next, p_t"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [],
   "source": [
    "def rnn_forward(X, Y, a0, parameters, vocab_size = 27):    \n",
    "    x, a, y_hat = {}, {}, {}\n",
    "    \n",
    "    a[-1] = np.copy(a0)\n",
    "    \n",
    "    loss = 0\n",
    "    \n",
    "    for t in range(len(X)):\n",
    "        x[t] = np.zeros((vocab_size,1)) \n",
    "        if (X[t] != None):\n",
    "            x[t][X[t]] = 1\n",
    "        a[t], y_hat[t] = rnn_step_forward(parameters, a[t-1], x[t])\n",
    "        \n",
    "        loss -= np.log(y_hat[t][Y[t],0])\n",
    "        \n",
    "    cache = (y_hat, a, x)        \n",
    "    return loss, cache"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [],
   "source": [
    "def rnn_step_backward(dy, gradients, parameters, x, a, a_prev):    \n",
    "    gradients['dWya'] += np.dot(dy, a.T)\n",
    "    gradients['dby'] += dy\n",
    "    da = np.dot(parameters['Wya'].T, dy) + gradients['da_next']\n",
    "    daraw = (1 - a * a) * da \n",
    "    gradients['db'] += daraw\n",
    "    gradients['dWax'] += np.dot(daraw, x.T)\n",
    "    gradients['dWaa'] += np.dot(daraw, a_prev.T)\n",
    "    gradients['da_next'] = np.dot(parameters['Waa'].T, daraw)\n",
    "    return gradients"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [],
   "source": [
    "def rnn_backward(X, Y, parameters, cache):\n",
    "    gradients = {}\n",
    "    \n",
    "    (y_hat, a, x) = cache\n",
    "    Waa, Wax, Wya, by, b = parameters['Waa'], parameters['Wax'], parameters['Wya'], parameters['by'], parameters['b']\n",
    "    \n",
    "    gradients['dWax'], gradients['dWaa'], gradients['dWya'] = np.zeros_like(Wax), np.zeros_like(Waa), np.zeros_like(Wya)\n",
    "    gradients['db'], gradients['dby'] = np.zeros_like(b), np.zeros_like(by)\n",
    "    gradients['da_next'] = np.zeros_like(a[0])\n",
    "    \n",
    "    for t in reversed(range(len(X))):\n",
    "        dy = np.copy(y_hat[t])\n",
    "        dy[Y[t]] -= 1\n",
    "        gradients = rnn_step_backward(dy, gradients, parameters, x[t], a[t], a[t-1])\n",
    "    \n",
    "    return gradients, a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [],
   "source": [
    "def update_parameters(parameters, gradients, lr):\n",
    "    parameters['Wax'] += -lr * gradients['dWax']\n",
    "    parameters['Waa'] += -lr * gradients['dWaa']\n",
    "    parameters['Wya'] += -lr * gradients['dWya']\n",
    "    parameters['b']  += -lr * gradients['db']\n",
    "    parameters['by']  += -lr * gradients['dby']\n",
    "    return parameters"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [],
   "source": [
    "def optimize(X, Y, a_prev, parameters, learning_rate = 0.01):\n",
    "    loss, cache = rnn_forward(X,Y,a_prev,parameters)\n",
    "    \n",
    "    gradients, a = rnn_backward(X,Y,parameters,cache)\n",
    "    \n",
    "    gradients = clip(gradients,5)\n",
    "    \n",
    "    parameters = update_parameters(parameters,gradients,learning_rate)    \n",
    "  \n",
    "    return loss, gradients, a[len(X)-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {},
   "outputs": [],
   "source": [
    "vocab_size, n_a = 27, 100\n",
    "a_prev = np.random.randn(n_a, 1)\n",
    "Wax, Waa, Wya = np.random.randn(n_a, vocab_size), np.random.randn(n_a, n_a), np.random.randn(vocab_size, n_a)\n",
    "b, by = np.random.randn(n_a, 1), np.random.randn(vocab_size, 1)\n",
    "parameters = {\"Wax\": Wax, \"Waa\": Waa, \"Wya\": Wya, \"b\": b, \"by\": by}\n",
    "X = [12,3,5,11,22,3]\n",
    "Y = [4,14,11,22,25, 26]\n",
    "\n",
    "loss, gradients, a_last = optimize(X, Y, a_prev, parameters, learning_rate = 0.01)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {},
   "outputs": [],
   "source": [
    "# loss, gradients, a_last"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 训练模型"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [],
   "source": [
    "def model(data, ix_to_char, char_to_ix, num_iterations = 35000, n_a = 50, dino_names = 7, vocab_size = 27):\n",
    "    n_x, n_y = vocab_size, vocab_size\n",
    "    \n",
    "    parameters = initialize_parameters(n_a, n_x, n_y)\n",
    "    \n",
    "    loss = -np.log(1.0/vocab_size)*dino_names\n",
    "    \n",
    "    with open(\"datasets/dinos.txt\") as f:\n",
    "        examples = f.readlines()\n",
    "    examples = [x.lower().strip() for x in examples]\n",
    "    \n",
    "    shuffle(examples)\n",
    "    \n",
    "    a_prev = np.zeros((n_a, 1))\n",
    "    \n",
    "    for j in range(num_iterations):\n",
    "\n",
    "        index = j%len(examples)\n",
    "        X = [None] + [char_to_ix[ch] for ch in examples[index]]\n",
    "        Y = X[1:] + [char_to_ix[\"\\n\"]]\n",
    "        \n",
    "        cur_loss, gradients, a_prev = optimize(X,Y,a_prev,parameters,learning_rate=0.01)  \n",
    "        # 平滑\n",
    "        loss = loss * 0.999 + cur_loss * 0.001\n",
    "\n",
    "        if j % 2000 == 0:            \n",
    "            print('Iteration: %d, Loss: %f' % (j, loss) + '\\n')\n",
    "            \n",
    "            for name in range(dino_names):\n",
    "                \n",
    "                sampled_indices = sample(parameters, char_to_ix)\n",
    "                txt = ''.join(ix_to_char[ix] for ix in sampled_indices)\n",
    "                txt = txt[0].upper() + txt[1:]\n",
    "                print ('%s' % (txt, ), end='')                    \n",
    "        \n",
    "    return parameters"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "outputs": [],
   "source": [
    "def initialize_parameters(n_a, n_x, n_y):\n",
    "    np.random.seed(1)\n",
    "    Wax = np.random.randn(n_a, n_x)*0.01 \n",
    "    Waa = np.random.randn(n_a, n_a)*0.01 \n",
    "    Wya = np.random.randn(n_y, n_a)*0.01\n",
    "    b = np.zeros((n_a, 1)) \n",
    "    by = np.zeros((n_y, 1))     \n",
    "    parameters = {\"Wax\": Wax, \"Waa\": Waa, \"Wya\": Wya, \"b\": b,\"by\": by}\n",
    "    \n",
    "    return parameters"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Iteration: 0, Loss: 23.084040\n",
      "\n",
      "Flcaudczarjdgswgikvtentlneqaijpyenupscvhkbrvmbbcmp\n",
      "Azglqsbbxhsslbxvklnjmlgwaitmumzw\n",
      "Lwiskbhhqyrhrbjerqiddfhwcdipafvqichfshrkiudlohsxadmuq\n",
      "Hqrmapmsjvhw\n",
      "Tvrxeifvtwidzlsqcvzziycyakvssgkojmnvsq\n",
      "Dwtdadvztu\n",
      "Wrimyaednfbmvr\n",
      "Iteration: 2000, Loss: 27.933262\n",
      "\n",
      "Arasaurus\n",
      "Hanpa\n",
      "Onis\n",
      "Gcanes\n",
      "Tos\n",
      "Glen\n",
      "Otaus\n",
      "Iteration: 4000, Loss: 25.906777\n",
      "\n",
      "Ngogitoritys\n",
      "Jgcanta\n",
      "Hoptosaura\n",
      "Doraptor\n",
      "Octxanoraus\n",
      "Rachaglytaten\n",
      "Onodiroroptinlonis\n",
      "Iteration: 6000, Loss: 24.653347\n",
      "\n",
      "Prohmolasaurus\n",
      "Miwenapelichosaurus\n",
      "\n",
      "Luanechesaurus\n",
      "Nascelopsobhonorseuruccidysaurus\n",
      "Biylosaurus\n",
      "\n",
      "Iteration: 8000, Loss: 24.111200\n",
      "\n",
      "Mwelashus\n",
      "Atotorkor\n",
      "Hieshossynzsaurunus\n",
      "Anisaurusuonduenodra\n",
      "Alosnhoconasauauskeldimaloaleileteranosaurus\n",
      "Chacilus\n",
      "Ianchiosaurus\n",
      "Iteration: 10000, Loss: 23.829090\n",
      "\n",
      "Cheventosaurus\n",
      "Ishosaurus\n",
      "Uroptosaurus\n",
      "Rleneryta\n",
      "Alynosaurus\n",
      "Carhyosbs\n",
      "Rasauson\n",
      "Iteration: 12000, Loss: 23.368544\n",
      "\n",
      "Jeetetosaurus\n",
      "Hugcosaurus\n",
      "Njnmurus\n",
      "Aropiamacroeia\n",
      "Scsaurus\n",
      "Qaxaradon\n",
      "Alchatorsaurus\n",
      "Iteration: 14000, Loss: 23.172871\n",
      "\n",
      "Locosaurus\n",
      "Pheusaurus\n",
      "Inoplonosaurus\n",
      "Lonosunephelophlinonykapenosmosodon\n",
      "Managromugonekchanidona\n",
      "Styuriosaurus\n",
      "Slenyfenqus\n",
      "Iteration: 16000, Loss: 23.232722\n",
      "\n",
      "Gooidon\n",
      "Mibitas\n",
      "Ongosaurus\n",
      "Hulotan\n",
      "Ppktreovados\n",
      "Aqdaetasaurus\n",
      "Ezisaurus\n",
      "Iteration: 18000, Loss: 22.966668\n",
      "\n",
      "Rihanimagosaurus\n",
      "Yragtonosaurus\n",
      "Srbpimaia\n",
      "Psahodon\n",
      "Sanosaurus\n",
      "Gjarlinasaurus\n",
      "Qgerthosaurus\n",
      "Iteration: 20000, Loss: 22.769614\n",
      "\n",
      "Angudosaurus\n",
      "Ydanojacropodra\n",
      "Tinachpalesaurus\n",
      "Douiosaurus\n",
      "Elocersalia\n",
      "Miviosaurus\n",
      "Hotovun\n",
      "Iteration: 22000, Loss: 22.889021\n",
      "\n",
      "Shacianop\n",
      "Hidixichoun\n",
      "Saurus\n",
      "Saurus\n",
      "Remoterosaurus\n",
      "Maggodontor\n",
      "Nogmanirus\n",
      "Iteration: 24000, Loss: 22.650315\n",
      "\n",
      "Saurionsaurus\n",
      "Skengjianlosaurus\n",
      "Vorritatah\n",
      "Ruchusuchus\n",
      "Goreosaurus\n",
      "Fnnosaurus\n",
      "Rnelolos\n",
      "Iteration: 26000, Loss: 22.638426\n",
      "\n",
      "Endiurus\n",
      "Enosaurus\n",
      "Scathamurataurus\n",
      "Spinitylmaraethubaspangennarosaurus\n",
      "Rawrax\n",
      "Loplimtothasaurus\n",
      "Elonghiroptor\n",
      "Iteration: 28000, Loss: 22.646872\n",
      "\n",
      "Paoddorantar\n",
      "Minatacisaurus\n",
      "Gystacia\n",
      "Piranioveratops\n",
      "Drazlangasaurosaurus\n",
      "Caavadol\n",
      "Ranibelba\n",
      "Iteration: 30000, Loss: 22.563345\n",
      "\n",
      "Rroshesaurus\n",
      "Erohunoturux\n",
      "Chytenodhhiinsthecelagosaurus\n",
      "Rusainnosaurus\n",
      "Ncalosaurus\n",
      "Proniosaurus\n",
      "Rakosaurus\n",
      "Iteration: 32000, Loss: 22.333833\n",
      "\n",
      "Blodosaurus\n",
      "Ydolopsqsilnodon\n",
      "Golia\n",
      "Hanoplapolosychesa\n",
      "Lotodon\n",
      "Elaphosaurus\n",
      "Yodovinaziiamosaurus\n",
      "Iteration: 34000, Loss: 22.369372\n",
      "\n",
      "Cangstahong\n",
      "Yloosaupus\n",
      "Caminasaurus\n",
      "Rotosaurus\n",
      "Rachodontaurhal\n",
      "Cngosaurus\n",
      "Craeosaurus\n"
     ]
    }
   ],
   "source": [
    "parameters = model(data, ix_to_char, char_to_ix)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 结尾\n",
    "1. 算法一开始生成的名字比较随机，随着迭代次数的增加，成本值不断缩小，生成的字符串看上去也越来越像恐龙的名字。\n",
    "2. 改进方向，增加迭代次数，增加训练集，调整超参数，使用更好的优化算法，etc；"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.5"
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": true,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {},
   "toc_section_display": true,
   "toc_window_display": false
  },
  "varInspector": {
   "cols": {
    "lenName": 16,
    "lenType": 16,
    "lenVar": 40
   },
   "kernels_config": {
    "python": {
     "delete_cmd_postfix": "",
     "delete_cmd_prefix": "del ",
     "library": "var_list.py",
     "varRefreshCmd": "print(var_dic_list())"
    },
    "r": {
     "delete_cmd_postfix": ") ",
     "delete_cmd_prefix": "rm(",
     "library": "var_list.r",
     "varRefreshCmd": "cat(var_dic_list()) "
    }
   },
   "types_to_exclude": [
    "module",
    "function",
    "builtin_function_or_method",
    "instance",
    "_Feature"
   ],
   "window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
